package com.leetcode.offer;

import java.util.HashSet;
import java.util.Set;

/**
 * @author zfl
 * @Classname FindRepeatNumber
 * @Description 数组中重复的数字
 * @Date 2020/10/14 14:07
 */
public class FindRepeatNumber {

    /**
     * @param nums
     * @return int
     * 执行用时：10 ms, 在所有 Java 提交中击败了15.79%的用户
     * 内存消耗：47.2 MB, 在所有 Java 提交中击败了43.44%的用户
     */
    public static int findRepeatNumber(int[] nums) {
        Set<Integer> set = new HashSet<>();
        int num = -1;
        for (int i = 0; i < nums.length; i++) {
            if(!set.contains(nums[i])) {
                set.add(nums[i]);
            }else {
                num = nums[i];
                break;
            }
        }
        return num;
    }

    /**
     * @param nums
     * @return
     * set.add()方法：如果添加的元素不存在，返回true,如果添加的元素存在，则返回false;
     */
    public int findRepeatNumber2(int[] nums) {
        Set<Integer> set = new HashSet<Integer>();
        int repeat = -1;
        for (int num : nums) {
            if (!set.add(num)) {
                repeat = num;
                break;
            }
        }
        return repeat;
    }

    /**
     * @param nums
     * @return
     * 原地置换
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：46.3 MB, 在所有 Java 提交中击败了88.64%的用户
     * 如果没有重复数字，那么正常排序后，数字i应该在下标为i的位置，所以思路是重头扫描数组，遇到下标为i的数字如果不是i的话，
     * （假设为m),那么我们就拿与下标m的数字交换。在交换过程中，如果有重复的数字发生，那么终止返回
     */
    public static int findRepeatNumber3(int[] nums) {
        int temp;
        for (int i = 0; i < nums.length; i++) {
            while (nums[i] != i) {
                if(nums[i] == nums[nums[i]]) {
                    return nums[i];
                }
                temp = nums[i];
                nums[i] = nums[temp];
                nums[temp] = temp;
            }
        }
        return -1;
    }
}
